package algo.A04_快速排序和归并排序;

import util.ArrayUtil;

import java.util.Random;

/**
 * 寻找发帖水王
 * Tango是微软亚洲研究院的一个试验项目。
 * 研究院的员工和实习生们都很喜欢在Tango上面交流灌水。
 * 传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。
 * 坊间风闻该“水王”发帖数目超过了帖子总数的一半。
 * 如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，
 * 你能快速找出这个传说中的Tango水王吗？
 */
public class T04_寻找发帖水王 {
    public static void main(String[] args) {
        int length = 10 + new Random().nextInt(10);
        int[] arr = ArrayUtil.getRandomArr(length, 0, 20);
        int r = new Random().nextInt(20);
        for (int i = 0; i < arr.length / 2 + new Random().nextInt(4); i++) {
            arr[i] = r;
        }
        ArrayUtil.shuffle(arr);
        ArrayUtil.print(arr);
        int result = solution(arr);
        System.out.println("result = " + result);
    }

    /*
        解题思路：定义一个候选变量和血量变量，血量为0时代表没有候选，血量>0时代表有候选
        (1)如果没有候选(血量==0)，则把当前遍历到的数作为候选，血量+1
        (2)如果有候选(血量>0)，则判断当前遍历到的数是否等于候选，若等于则血量+1，否则血量-1
        遍历结束后若血量大于0，则当前候选为水王，否则没有水王
     */
    private static int solution(int[] arr){
        int candidate = -1;
        int hp = 0;
        for (int i : arr) {
            if (hp == 0) {
                candidate = i;
                hp++;
            } else if (i == candidate) {
                hp++;
            } else {
                hp--;
            }
        }
        if (hp > 0){
            return candidate;
        }else {
            return -1;
        }
    }
}
